/**
 * 494.目标和
 */
public class Exerciser3 {
    // 为了查找target这个值，把这个数组分成两份，一份是一些数均为正数，另一份数是一些事数均为负数
    // 这样第一份的 和为a，第二份的 绝对值的和为b
    // a - b = target
    // a + b = sum
    // a = (target+sum)/2

    /**
     * 滚动数组优化
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        // 滚动数组优化
        int n = nums.length;
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        int aim = (sum + target) / 2;
        if (aim < 0 || (sum + target) % 2 == 1) {
            return 0;
        }
        // dp[i][j]: 从前i个数选取值，所选的值的和 正好等于j，一共有多少种选法
        int[] dp = new int[aim + 1];
        // 初始化
        dp[0] = 1;
        for(int i = 1;i <= n;i++) {
            for(int j = aim;j >= nums[i - 1];j--) {
                dp[j] += dp[j - nums[i - 1]];
            }
        }
        return dp[aim];
    }

    public int findTargetSumWays1(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        int aim = (sum + target) / 2;
        if (aim < 0 || (sum + target) % 2 == 1) {
            return 0;
        }
        // dp[i][j]: 从前i个数选取值，所选的值的和 正好等于j，一共有多少种选法
        int[][] dp = new int[n + 1][aim + 1];
        // 初始化
        dp[0][0] = 1;
        // dp[1~n][0] 不用初始化，因为dp[1~n][0] 位置的j值(0)是小于等于nums[0~n-1]位置的值的，
        // 所以执行dp[i][j] = dp[i - 1][j];也就是上一个位置的值，即使nums[i - 1]为0的话，那么j-nums[i- 1]也会等于0
        for(int i = 1;i <= n;i++) {
            for(int j = 0;j <= aim;j++) {
                dp[i][j] = dp[i - 1][j];
                if(j >= nums[i - 1]) {
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][aim];
    }
}
